"""
算法：哈夫曼树
输入：字典{字符：出现频次}
输出：哈夫曼树/字典{字符：01编码}
————————————————————————————
贪心算法
当只有当前一个树时退出算法
每次对现有结点树的频数进行排序
每次选取最小和次小的合并为新子树，频数为二者之和
"""

from MergeSort import MergeSort


class HfmTree:
    def __init__(self, *args):
        if args.__len__() == 2:
            self.char = args[0]
            self.num = args[1]
        else:
            #    合并后的新子树无字符仅有频数
            self.char = None
            self.num = args[0]

        # self.char, self.num = char, num
        self.left, self.right, self.code = None, None, ''

    def __add__(self, other):
        newtree = HfmTree(self.num + other.num)
        newtree.left = self
        newtree.right = other
        return newtree

    def __lt__(self, other):
        return self.num < other.num

    def __gt__(self, other):
        return self.num > other.num

    def __eq__(self, other):
        return self.num == other.num and self.char == other.char

    def __str__(self):
        return (
            "\nchar: {}; num: {}; code: {}; left: {}; right: {};\n".format(self.char, self.num, self.code, self.left,
                                                                           self.right))


# 字符串转字典
def getDict(input_str):
    dict = {}
    for item in set(input_str):
        dict[item] = input_str.count(item)
    return dict


# 字典转数结点列表
def toHfmTreeList(dict):
    treeList = []
    for item in dict.keys():
        treeList.append(HfmTree(item, dict[item]))
    return treeList


# 算法实现
def GetHfmTree(treelist, dict=None):
    if treelist.__len__() < 2:
        GetHfmCode(treelist[0], dict)
        return treelist[0]
    MergeSort(treelist, 0, treelist.__len__() - 1)
    treelist.append(treelist[0] + treelist[1])
    del treelist[0]
    del treelist[0]
    # 这里踩坑！del删除会导致原来在被删除元素后面的元素位置前移
    return GetHfmTree(treelist, dict)


# 在HfmTree内调用
def GetHfmCode(hfmTree, dict=None):
    if hfmTree is None:
        print(hfmTree)
        return
    if hfmTree.left is not None:
        hfmTree.left.code = hfmTree.code + '0'
        GetHfmCode(hfmTree.left, dict)
    else:
        #     左子树为空可能是叶子结点
        if hfmTree.char is not None:
            dict[hfmTree.char] = hfmTree.code
    if hfmTree.right is not None:
        hfmTree.right.code = hfmTree.code + '1'
        GetHfmCode(hfmTree.right, dict)
    else:
        #     右子树为空可能是叶子结点
        if hfmTree.char is not None:
            dict[hfmTree.char] = hfmTree.code


# 输入字符串输出哈夫曼的字符编码字典
def runHfmAlgorithm(input_str: str):
    dict = {}
    GetHfmTree(toHfmTreeList(getDict(input_str)), dict)
    for item in set(input_str):
        input_str = input_str.replace(item, dict[item])
    return dict, input_str


if __name__ == "__main__":
    str = "aaaddddqweeeeeeeeeeee"
    print(runHfmAlgorithm(str))
    print(str)
